21. Pentru generarea tuturor mulţimilor de câte 5 cifre, având la dispoziţie cifrele de la 1 la 9 , se poate utilza un algoritm echivalent cu algoritmul de generare a:
a. permutărilor de 5 elemente
b. submulţimilor mulţimii {1,2,3,4,5,6,7,8,9}
c. combinărilor de 9 elemente luate câte 5
d. aranjamentelor de 9 elemente luate câte 5
Raspuns: c)

22. Utilizăm metoda backtracking pentru generarea tuturor modalităţilor de a scrie numărul 9 ca sumă a cel puţin două numere naturale nenule distincte. Termenii descompunerii sunt în ordine strict crescătoare. Soluţiile se generează în ordinea: 1+2+6, 1+3+5, 1+8, 2+3+4, 2+7, 3+6 şi 4+5. Se aplică exact aceeaşi metodă pentru scrierea lui 12 . Scrieţi în ordine toate soluţiile de forma 2+... ?
Raspuns: 2+3+7*2+4+6 ; 2+10

23. Se utilizează un algoritm pentru a genera în ordine lexicografică inversă toate permutările mulţimii { 1 , 2 , 3 , 4 , 5 }. Primele patru permutări generate sunt: 54321 , 54312 , 54231 , 54213. A cincea permutare este:
a. 53421
b. 54321
c. 54132
d. 54123
Raspuns: c)

24. Utilizăm metoda backtracking pentru generarea tuturor modalităţilor de a scrie numărul 9 ca sumă a cel puţin două numere naturale nenule distincte. Termenii descompunerii sunt în ordine strict crescătoare. Soluţiile se generează în ordinea: 1+2+6, 1+3+5, 1+8, 2+3+4, 2+7, 3+6 şi 4+5. Se aplică exact aceeaşi metodă pentru scrierea lui 8 . Câte soluţii vor fi generate?
a. 3
b. 4
c. 6
d. 5
Raspuns: d)

25. Utilizăm metoda backtracking pentru generarea tuturor modalităţilor de a scrie numărul 6 ca sumă a cel puţin două numere naturale nenule. Termenii descompunerii sunt în ordine crescătoare. Soluţiile se generează în ordinea: 1+1+1+1+1+1, 1+1+1+1+2, 1+1+1+3, 1+1+4, 1+5, 2+2+2, 2+4 şi 3+3. Se aplică exact aceeaşi metodă pentru scrierea lui 9 . Care este penultima soluţie?
a. 3+3+3
b. 3+6 c. 4+5
d. 2+7

Raspuns:b)

26. Utilizăm metoda backtracking pentru generarea tuturor modalităţilor de a scrie numărul 6 ca sumă a cel puţin două numere naturale nenule. Termenii descompunerii sunt în ordine crescătoare. Soluţiile se generează în ordinea: 1+1+1+1+1+1, 1+1+1+1+2, 1+1+1+3, 1+1+4, 1+5, 2+2+2, 2+4 şi 3+3. Se aplică exact aceeaşi metodă pentru scrierea lui 9 . Câte soluţii de forma 2+... vor fi generate?
a. 2
b. 3
c. 4 d. 5

Raspuns: c)

27. Utilizând metoda backtracking se generează numerele naturale formate din exact 3 cifre şi care au suma cifrelor egală cu 4, în această ordine: 103, 112, 121, 130, 202, 211, 220, 301, 310, 400 . Dacă utilizăm acelaşi algoritm pentru a genera toate numerele de 4 cifre ce au suma cifrelor egala cu 7 precizaţi care este numarul generat imediat dupa 1222.
a. 1231
b. 1223
c. 1213
d. 1321

28. Utilizând metoda backtracking se generează toate permutările mulţimii {1,2,3,4} . Dacă primele trei permutări generate sunt, în acestă ordine: 1234, 1243, 1324 precizaţi care este permutarea generată imediat după 3412 .
a. 3421
b. 3413
c. 4123
d. 3214
Raspuns: a)

29. Utilizând metoda backtracking se generează numerele formate din câte 3 cifre distincte din mulţimea {1,3,5,7} . Dacă primele trei numere generate sunt, în acestă ordine: 135, 137,153 care este cel de-al patrulea număr generat?
a. 157
b. 173
c. 315
d. 357
Raspuns: a)

30. Utilizând metoda backtracking se generează permutările cuvântului info . Dacă primele trei soluţii generate sunt: fino, fion, fnio care este cea de-a cincea soluţie?
a. foin
b. fnoi
c. foni
d. ifon

Raspuns: a)

31. Utilizând metoda backtracking se generează toate cuvintele de câte 3 litere din mulţimea {a,b,c} . Dacă primele patru cuvinte generate sunt, în acestă ordine: aaa, aab, aac, aba, care este cel de-al optulea cuvânt generat?
a. acb
b. acc
c. aca
d. bca<
Raspuns: a)

32. Un program generează, în ordine crescătoare, numerele naturale, de exact 5 cifre din mulţimea { 1 , 2 , 3 , 4 , 5} . Fiecare dintre numerele generate are cifrele distincte două câte două. Primele 3 numere astfel generate sunt: 12345 , 12354 , 12435 . Care este numărul generat imediat după 12543 ?
a. 15342
b. 12534
c. 13245
d. 13452
Raspuns: c)

33. Într-un penar sunt unsprezece creioane, dintre care trei sunt roşii iar celelalte sunt negre. Dacă scoatem din penar cinci creioane, câte posibilităţi există ca două dintre ele să fie roşii?
Raspuns: 168

34.  Se generează în ordine strict crescătoare numerele de câte şase cifre care conţin: cifra 1 o singură dată, cifra 2 de două ori şi cifra 3 de trei ori. Se obţin, în această ordine, numerele: 122333 , 123233 , 123323 , …, 333221 . Câte numere generate prin această metodă au prima cifră 1 şi ultima cifră 2 ?
Raspuns: 122333, 123233, 123323, 123332 , 132332 ,132323, 132233, 133223, 133232 , 133322=> 4 numere

35.  Se generează în ordine strict crescătoare toate numerele de câte şase cifre care conţin: cifra 1 o singură dată, cifra 2 de două ori şi cifra 3 de trei ori. Se obţin, în această ordine, numerele: 122333 , 123233 , 123323 , …, 333221 . Ce număr se generează imediat după 332312 ?
Raspuns: 332321

36.  Se consideră un număr natural nenul x având exact 8 cifre, cifrele lui fiind distincte 2 câte 2 , iar printre cifrele sale se găseşte şi cifra 0 . Permutând cifrele lui x se obţin alte numere naturale. Câte dintre numerele obţinute, inclusiv x , au exact 8 cifre?
Raspuns: Numarul de permutari pentru un numar de 8 cifre este 8!. Din acestea se scad cele cu cifra 0 pe prima pozitie,adica7!.
8!-7!=35280.

37.   Utilizând metoda backtracking se generează în ordine lexicografică toate anagramele cuvântului caiet ( cuvinte formate din aceleaşi litere, eventual în altă ordine). Câte cuvinte vor fi generate?
Rezolvare: Permutari de n litere. Cuvantul are 5 litere. P5=5!=1*2*3*4*5=120.

38. Utilizând metoda backtracking se generează în ordine lexicografică toate anagramele cuvântului caiet ( cuvinte formate din aceleaşi litere, eventul în altă ordine). Care este a şasea soluţie?
a. catei
b. actie
c. actei
d. catie

Rezolvare: caiet, caite, caeti, caeit, catei, catie

39. Utilizând metoda backtracking se generează toate matricele pătratice de ordinul 4 ale căror elemente aparţin mulţimii {0,1} cu proprietatea că pe fiecare linie şi pe fiecare coloană există o singură valoare 1 . Primele 3 soluţii generate sunt, în această ordine:
1 0 0 0
1 0 0 0
1 0 0 0
0 1 0 0

0 1 0 0
0 0 1 0
0 0 1 0
0 0 1 0

0 1 0 0
0 0 0 1
0 0 0 1
0 0 0 1.
Care este penultima soluţie?

a. 0 0 0 1
    0 0 1 0
    1 0 0 0
    0 1 0 0

b. 0 1 0 0
    1 0 0 0
    0 0 1 0
    0 0 0 1

c. 0 0 0 1
    0 1 0 0
    0 0 1 0
    1 0 0 0

d. 0 0 1 0
    1 0 0 0
    0 1 0 0
    0 0 0 1

Raspuns: a

40. Pentru a genera toate numerele naturale cu exact 4 cifre şi care au cifrele în ordine strict descrescătoare, se poate utiliza un algoritm echivalent cu cel pentru generarea:
a. aranjamentelor de 4 obiecte luate câte 10
b. combinărilor de 10 obiecte luate câte 4
c. permutărilor a 10 obiecte
d. permutărilor a 4 obiecte

Raspuns: b

41. Se utilizează metoda backtracking pentru a genera toate cuvintele de câte patru litere distincte din mulţimea {d,a,n,s} . Ştiind că al doilea cuvânt generat este dans , iar al treilea este dsan , care va fi ultimul cuvânt obţinut?
a. nsad
b. snad
c. snda
d. dans
dasn, dans, dsan, dnsa, dnas,…., nsad
Raspuns: a

42. Se utilizează metoda backtracking pentru a genera toate cuvintele de câte trei litere distincte din mulţimea {i,n,f,o} . Ştiind că ultimele trei cuvinte generate sunt, în ordine, ion , inf şi ino , care este cel de-al doilea cuvânt obţinut?
a. ofn
b. ifo
c. foi
d. nif
Raspuns: c.

43. Se utilizează metoda backtracking pentru a genera toate cuvintele care conţin toate literele din mulţimea {i,n,f,o} , astfel încât fiecare literă să apară exact o dat într-un cuvânt. Ştiind că al doilea cuvânt generat este info iar al treilea este ionf , care este ultimul cuvânt obţinut?
a. nifo
b. ofni
c. ofin
d. foni
Raspuns: d.

44. Se utilizează metoda backtracking pentru a genera toate cuvintele care conţin toate literele din mulţimea {i,n,f,o} , astfel încât fiecare literă să apară exact o data într-un cuvânt şi literele n şi o să nu se afle pe poziţii vecine. Ştiind că primul cuvânt generat este info , iar al treilea este nifo care este cel de-al doilea cuvânt obţinut?
a. iofn
b. inof
c. ionf
d. niof
Raspuns: d.

45. Generarea matricelor pătratice de ordinul n , cu elemente 0 şi 1 , cu proprietatea că pe fiecare linie şi pe fiecare coloană există un singur element egal cu 1 , se poate realiza utilizând metoda backtracking. Algoritmul utilizat este echivalent cu algoritmul de generare a:
a. combinărilor
b. permutărilor
c. aranjamentelor
d. produsului cartezian

Raspuns: d.

46. Se utilizează metoda backtracking pentru a genera toate cuvintele care conţin toate literele din mulţimea {i,n,f,o}, astfel încât fiecare literă să apară exact o data într-un cuvânt. Ştiind că al doilea cuvânt generat este info iar al treilea este ionf, care este ultimul cuvânt obţinut? a. nifo
b. ofni
c. ofin
d. foni Daca al 2-lea cuvant generat din multimea {info} este info si al treilea cuvant generat este ionf=> ca primul cuvant generat este inof iar al 4-lea este iofn. De la primul cuvant observam ca ultimele 4 cuvinte generate vor incepe cu f ,prin eliminare ,ultimul cuvant va fi foni.
Raspuns: d.

47. Generarea matricelor p ătratice de ordinul n, cu elemente 0 şi 1, cu proprietatea că pe fiecare linie şi pe fiecare coloană există un singur element egal cu 1, se poate realiza utilizând metoda backtracking. Algoritmul utilizat este echivalent cu algoritmul de generare a:
a. combinărilor
b. permutărilor
c. aranjamentelor
d. produsului cartezian
Raspuns: b.
Prin definitie, metoda backtracking poate fi asociata cu permutarile.

48.Se generează, prin metoda backtracking toate partiţiile mulţimii A={1,2,3} obţinându-se următoarele soluţii: {1}{2}{3}; {1}{2,3}; {1,3}{2}; {1,2}{3}; {1,2,3}. Se observă că dintre acestea, prima soluţie e alcătuită din exact trei submulţimi. Dacă se foloseşte aceeaşi metodă pentru a genera partiţiile mulţimii {1,2,3,4} stabiliţi câte dintre soluţiile generate vor fi alcătuite din exact trei submulţimi.
a. 3
b. 12
c. 6
d. 5
Raspuns: c.
Generand fiecare solutie din submultimea A, vom obtine exact 6 solutii a cate 3 submultimi.

49. Se generează, prin metoda backtracking, toate modalităţile de aşezare a numerelor naturale de la 1 la 5, astfel încât oricare 2 numere consecutive s ă nu se afle pe poziţii alăturate. Dacă primele 2 soluţii sunt: (1,3,5,2,4) şi (1,4,2,5,3), care este prima soluţie generată în care primul număr este 4?
a. (4, 1, 3, 2, 5)
b. (4, 2, 5, 1, 3)
c. (4, 3, 5, 3, 1)
d.(4, 1, 3, 5, 2)
Raspuns: d.
Dupa 4 trebuie sa fie neaparat 1 ,ramane A si D. La A ai pe pozitia 2 si 3 numere consecutive deci sare..inseamna ca a mai ramas D.